﻿package linearList;

public class LinkedList<T> implements ILinkedList<T> {
    private Node<T> head;

    public LinkedList() {
        this.head = new Node<>();
    }

    public LinkedList(T[] values) {
        this();
        Node<T> p = this.head;
        for (T data : values) {
            p.next = new Node<T>(data, null);
            p = p.next;
        }
    }

    public static void main(String[] args) {
        System.out.println("--测试初始化--");
        Integer[] data = {66, 33, 15, 11, 78, 4, 6, 9, 6, 10};
        LinkedList<Integer> linkedList = new LinkedList<Integer>(data);
        System.out.println(linkedList);

        System.out.println("测试长度");
        System.out.println(linkedList.size());

        System.out.println("--测试getNode 5, 0, 100--");
        Node<Integer> node5 = linkedList.getNode(5);
        System.out.println(node5);
        Node<Integer> node0 = linkedList.getNode(0);
        System.out.println(node0);
        Node<Integer> node100 = linkedList.getNode(100);
        System.out.println(node100);

        System.out.println("--测试insert(2, 22)--");
        linkedList.insert(2, 22);
        System.out.println(linkedList);

        System.out.println("--测试insert 10个元素--");
        for (int i = 20; i <= 30; i++) {
            linkedList.insert(i);
        }
        System.out.println(linkedList);

        System.out.println("--测试remove index为5的元素--");
        linkedList.remove(5);
        System.out.println(linkedList);

        System.out.println("--测试获取 index为5的元素--");
        System.out.println(linkedList.get(5));

        System.out.println("--测试设置 index为5的元素为100--");
        linkedList.set(5, 100);
        System.out.println(linkedList);

        System.out.println("--测试查找元素等于100--");
        System.out.println(linkedList.search(100));

        System.out.println("--测试remove by key--");
        linkedList.removeByKey(100);
        System.out.println(linkedList);

    }
    /**
     * 获取索引i节点，超出范围返回null
     * @param i 索引，从0开始
     * @return
     */
    private Node<T> getNode(int i) {
        Node<T> p = this.head.next;
        if(i >= 0) {
            for(int j=0;p.next!=null;p = p.next) {
                if(j == i) {
                    return p;
                }
                j++;
            }
        }
        return null;
    }

    @Override
    public boolean isEmpty() {
        return this.head.next==null;
    }

    @Override
    public int size() {

        Node<T> p=this.head.next;
        int i;
        for(i=0;p!=null;p=p.next) {
            i++;
        }
        return i;
    }

    @Override
    public T get(int i) {
        Node<T> p = this.head.next;

        if(i>=0 && i<=size()) {
            int j=0;
            while(i!=j++) {
                p=p.next;
            }
            return p.data;
        }
        return null;
    }

    @Override
    public void set(int i, T x) {
        Node<T> p = this.head.next;

        if(i>=0 && i<=size()) {
            int j=0;
            while(i!=j++) {
                p=p.next;
            }
            p.data=x;
        }

    }

    @Override
    public Node<T> insert(int i, T x) {

        Node<T> p = this.getNode(i);
        Node<T> front = this.getNode(i-1);
        Node<T> add = new Node<T>(x, null);
        front.next = add;
        add.next = p;
        return add;

    }

    @Override
    public Node<T> insert(T x) {

        Node<T> p = this.head.next;
        for(;p.next!=null;p = p.next);
        p.next = new Node<T>(x, null);
        return p;
    }

    @Override
    public T remove(int i) {

        if(i > 0) {
            this.getNode(i - 1).next = this.getNode(i + 1);
        } else if (i == 0) {
            this.head.next = this.head.next.next;
        }
        return null;

    }

    @Override
    public void clear() {
        this.head.next=null;

    }

    @Override
    public Node<T> search(T key) {
        Node<T> p = this.head.next;
        for(int j=0;p!=null;p = p.next) {
            if(p.data == key) {
                return new Node<T>((T)(Integer)j, null);
            }
            j++;
        }
        return null;
    }

    @Override
    public T removeByKey(T key) {

        return this.remove( (Integer)this.search(key).data);

    }

    public String toString() {
        String back = "";
        Node<T> p = this.head.next;
        for(;p!=null;p = p.next) {
            back += "\t" + p.data;
        }
        back += "\n";
        if(back.equals("\n")) {
            return "\tnull";
        }
        return back;
    }
}